/// 动态数组（ArrayList）实现，支持自动调整容量以容纳更多元素。
///
/// 内部使用 Vec<T> 作为存储容器，自动处理内存分配和容量扩展。
/// 通过泛型参数 T 实现类型安全，并派生常用标准特性。
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ArrayList<T> {
    /// 存储元素的动态数组容器
    /// 存储元素的动态数组容器
    pub data: Vec<T>,
}

impl<T> ArrayList<T> {
    /// 创建一个具有指定初始容量的动态数组
    ///
    /// # 参数
    /// - `capacity`: 初始容量设置。当输入值为0时，自动使用默认容量16
    ///
    /// # 返回值
    /// 返回初始化完成的 ArrayList 实例，底层使用 Vec::with_capacity 进行初始化
    pub fn new(capacity: usize) -> Self {
        let initial_capacity = if capacity == 0 { 16 } else { capacity };
        ArrayList {
            data: Vec::with_capacity(initial_capacity)
        }
    }
}

impl<T> ArrayList<T> {
    /// 移除指定索引范围内的元素
    ///
    /// # 参数
    /// - `index`: 起始索引（必须 ≤ 当前长度）
    /// - `length`: 要移除的元素数量（必须满足 index + length ≤ 当前长度）
    ///
    /// 当参数范围无效时无操作
    pub fn remove_range(&mut self, index: usize, length: usize) {
        if let Some(end) = index.checked_add(length) {
            if end <= self.data.len() {
                self.data.drain(index..end);
            }
        }
    }

    /// 移除单个元素
    ///
    /// # 参数
    /// - `index`: 要移除元素的索引（必须 < 当前长度）
    ///
    /// 当索引无效时无操作
    pub fn remove(&mut self, index: usize) {
        if index < self.data.len() {
            self.data.remove(index);
        }
    }
}

impl<T> ArrayList<T> {
    /// 清空数组但保留容量
    ///
    /// 等效于设置内部向量的长度为0，保留已分配内存
    pub fn clear(&mut self) {
        self.data.clear();
    }

    /// 查找元素的第一个匹配索引
    ///
    /// # 参数
    /// - `value`: 要查找的元素引用（通过 PartialEq 实现比较）
    ///
    /// # 返回值
    /// 返回 `Some(usize)` 包含匹配索引，或 `None` 表示未找到
    pub fn index_of(&self, value: &T) -> Option<usize>
    where
        T: PartialEq,
    {
        self.data.iter().position(|x| x == value)
    }
}

impl<T> ArrayList<T> {
    /// 使用自定义比较函数对动态数组进行排序
    ///
    /// # 参数
    /// - `compare_func`: 比较函数，返回 `std::cmp::Ordering` 类型
    pub fn sort_by<F>(&mut self, compare_func: F)
    where
        F: FnMut(&T, &T) -> std::cmp::Ordering,
    {
        self.data.sort_by(compare_func);
    }

    /// 对实现 Ord trait 的元素进行自然顺序排序
    pub fn sort(&mut self)
    where
        T: Ord,
    {
        self.data.sort();
    }
}

impl<T> ArrayList<T> {
    /// 在指定索引处插入元素
    ///
    /// # 参数
    /// - `index`: 插入位置索引，必须不大于当前长度（0 <= index <= len）
    /// - `value`: 要插入的元素值
    ///
    /// # 返回值
    /// 成功插入返回 `true`，索引越界返回 `false`
    pub fn insert(&mut self, index: usize, value: T) -> bool {
        if index > self.data.len() {
            return false;
        }

        // 显式实现双倍扩容策略以保持与原始C代码一致
        if self.data.len() + 1 > self.data.capacity() {
            let current_capacity = self.data.capacity();
            let new_capacity = current_capacity.saturating_mul(2).max(16);
            self.data.reserve(new_capacity.saturating_sub(current_capacity));
        }

        self.data.insert(index, value);
        true
    }
}

impl<T> ArrayList<T> {
    /// 在动态数组末尾追加元素
    ///
    /// # 参数
    /// - `value`: 要追加的元素值
    ///
    /// # 返回值
    /// 成功追加返回 `true`（始终成功）
    pub fn append(&mut self, value: T) -> bool {
        self.insert(self.data.len(), value)
    }

    /// 在动态数组头部插入元素
    ///
    /// # 参数
    /// - `value`: 要插入的元素值
    ///
    /// # 返回值
    /// 成功插入返回 `true`，索引越界返回 `false`
    pub fn prepend(&mut self, value: T) -> bool {
        self.insert(0, value)
    }
}